BIT Algo/2. Zajęcia/Zadanie 9. (Najczęściej powtarzający się spójny podciąg długości k).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Dane jest słowo, będące tablicą o długości $ n $, składającej się ze znaków z alfabetu $ E $ o rozmiarze $ |E| $. Dana jest również liczba $ k $. Długość słowa wynosi co najmniej $ |E|^k $ ($ n \\ge |E|^k $). Zaproponuj algorytm, który zwróci najczęściej powtarzający się w tym słowie spójny pociąg o długości $ k $. Algorytm ma działać w czasie $ O(n) $, wykorzystywać $ O(1) $ pamięci. Ponadto, zawartość tablicy po wykonaniu algorytmu powinna pozostać niezmieniona."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Uwagi"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Aby jakkolwiek zadanie było wykonalne, musimy założyć, że możliwa jest konwersja litery na liczbę, przedstawiającą jej pozycję w alfabecie, w czasie $ O(1) $ oraz konwersja w drugą stronę w tym samym czasie. Z tego powodu zakładam, że alfabet jest reprezentowany, przy pomocy klasy, która wykonuje obie operacje w czasie liniowym."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Implementacja klasy, reprezentującej alfabet "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Alphabet:\n",
    "    def __init__(self, characters):\n",
    "        self.chars_to_codes = {char:code for code, char in enumerate(characters)}\n",
    "        self.codes_to_chars = list(characters)\n",
    "        \n",
    "    def __repr__(self):\n",
    "        return f'{self.__class__.__name__}({\"\".join(self.codes_to_chars)})'\n",
    "        \n",
    "    def __str__(self):\n",
    "        return '\\n'.join(f'{char}: {code}' for char, code in self.chars_to_codes.items())\n",
    "    \n",
    "    def __iter__(self):\n",
    "        yield from self.codes_to_chars\n",
    "    \n",
    "    def __len__(self):\n",
    "        return len(self.chars_to_codes)\n",
    "    \n",
    "    def __getitem__(self, idx):\n",
    "        return self.chr(idx)\n",
    "    \n",
    "    def ord(self, char):\n",
    "        # If doesn't exist, None will be returned\n",
    "        return self.chars_to_codes.get(char)\n",
    "    \n",
    "    def chr(self, code):\n",
    "        # If a code is not valid, None will be returned\n",
    "        return self.codes_to_chars[code] if 0 <= code < len(self.codes_to_chars) else None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "##### Algorytm z zadania"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def most_common_substring(string: list, alphabet: 'alphabet class', k: 'length of a substring') -> (str, int):\n",
    "    # In the first loop encode all the substrings of length k (we will store codes of substrings\n",
    "    # shorter than k on indices before k-1 index as there are no enough letters to create\n",
    "    # a k-element substring)\n",
    "    \n",
    "    limit = len(alphabet) ** k\n",
    "    # Store a code of the first value in the first position\n",
    "    string[0] = alphabet.ord(string[0])\n",
    "    \n",
    "    for i in range(1, len(string)):\n",
    "        string[i] = encode_substring(string[i-1], string[i], limit, alphabet)\n",
    "        \n",
    "    # Using counting sort approach, store couns of each encoded substring in a string array.\n",
    "    # As we have to remember the initial codes, we will increase each code by the limit value\n",
    "    # if we encounter another substring with the same code\n",
    "    for i in range(len(string)):\n",
    "        # Retrieve the initial code of a substring\n",
    "        substring_code = counter_to_code(string[i], limit)\n",
    "        # Icrease a counter code of this substring in a string array\n",
    "        string[substring_code] += limit\n",
    "        \n",
    "    # Find the greatest value of a counter\n",
    "    max_count = 0\n",
    "    max_count_code = 0\n",
    "    for i in range(len(string)):\n",
    "        # Retrieve a value of a counter\n",
    "        count = get_count_from_counter(string[i], limit)\n",
    "        # Update the max_count and max_count_idx variables if found a substring which occurs\n",
    "        # more often\n",
    "        if count > max_count:\n",
    "            max_count = count\n",
    "            max_count_code = i\n",
    "            \n",
    "    # Bring back the initial values of a string array\n",
    "    curr_code = counter_to_code(string[-1], limit)\n",
    "    for i in range(len(string)-1, 0, -1):\n",
    "        prev_code = counter_to_code(string[i-1], limit)\n",
    "        curr_char = decode_substring(prev_code, curr_code, limit, alphabet)\n",
    "        string[i] = curr_char\n",
    "        curr_code = prev_code\n",
    "        \n",
    "    # Decode the first character\n",
    "    first_code = counter_to_code(string[0], limit)\n",
    "    string[0] = decode_substring(0, first_code, limit, alphabet)\n",
    "\n",
    "    # Return a substring with the most occurrences and a number of its repetitions\n",
    "    # We will use an array to store strings characters and then join them together as\n",
    "    # it is far faster than a string concatenation\n",
    "    return decode_substring_with_code(max_count_code, limit, alphabet), max_count\n",
    "        \n",
    "\n",
    "def encode_substring(prev_code: 'code of a previous encoded substring', \n",
    "                     curr_char: 'code of a current character', \n",
    "                     code_limit: 'limit value',\n",
    "                     alphabet: 'Alphabet class instance') -> int:\n",
    "    \"\"\"\n",
    "    This function creates a code of a substring based on a code of the previous substring\n",
    "    and a new character. This code always will be lower than code_limit as code_limit is\n",
    "    dependent on the max number of substring's characters. The idea of encoding a substring\n",
    "    is to treat this substring as a number in base of the alphabet's length. Encodins a substring\n",
    "    is an equivalent of converting a hexadecimal number to the decimal representation but in this\n",
    "    case we don't use base 16 and use different characters from our alphabet.\n",
    "    \"\"\"\n",
    "    base = len(alphabet)\n",
    "    char_code = alphabet.ord(curr_char)\n",
    "    # Shift all values to the left by multiplying a code of the previous substring by the base\n",
    "    # of our system (dictionary length) and add a code of the new character on the least\n",
    "    # significant bit's position and then drop the first character if a code of a new substring\n",
    "    # exceeds the biggest possible code.\n",
    "    return (prev_code * base + char_code) % code_limit\n",
    "\n",
    "\n",
    "def decode_substring(prev_code: 'code of a previous encoded substring', \n",
    "                     curr_code: 'code of a current substring', \n",
    "                     code_limit: 'limit value',\n",
    "                     alphabet: 'Alphabet class instance') -> int:\n",
    "    \"\"\"\n",
    "    This function retrieves a code of a single character which was added to the substring after\n",
    "    the previous substring. prev_code (a code of a previous substring) is required in order to\n",
    "    get a value of a single character which was next added.\n",
    "    \"\"\"\n",
    "    base = len(alphabet)\n",
    "    # Subtract a previous code shifted to the left from the current code in order to get the code\n",
    "    # Of a value which was added last.\n",
    "    char_code = curr_code - (prev_code * base) % code_limit\n",
    "    return alphabet.chr(char_code)\n",
    "\n",
    "\n",
    "def counter_to_code(counter_value: 'value of a substring counter',\n",
    "                    code_limit: 'limit value') -> int:\n",
    "    \"\"\"\n",
    "    As we will store counts of repeated substring as codes increased by a proper multiple\n",
    "    of the code_limit, this function will help us retrieve the initial code of an encoded\n",
    "    substring.\n",
    "    \"\"\"\n",
    "    return counter_value % code_limit\n",
    "\n",
    "\n",
    "def get_count_from_counter(counter_value: 'value of a substring counter',\n",
    "                           code_limit: 'limit value') -> int:\n",
    "    \"\"\"\n",
    "    As we will store counts of repeated substring as codes increased by a proper multiple\n",
    "    of the code_limit, this function will help us retrieve the real count of the substring\n",
    "    which will be equal to the number of times we increased a code by the code_limit.\n",
    "    \"\"\"\n",
    "    return counter_value // code_limit\n",
    "\n",
    "\n",
    "def decode_substring_with_code(substring_code: 'code of a substring to decode',\n",
    "                               code_limit: 'limit value',\n",
    "                               alphabet: 'Alphabet class instance') -> int:\n",
    "    \"\"\"\n",
    "    This function retrieves a string from its code.\n",
    "    \"\"\"\n",
    "    base = len(alphabet)\n",
    "    chars = []\n",
    "    \n",
    "    while code_limit > 1:\n",
    "        substring_code, char_code = divmod(substring_code, base)\n",
    "        chars.append(alphabet.chr(char_code))\n",
    "        code_limit //= base\n",
    "        \n",
    "    return ''.join(chars[::-1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "\n",
    "def test(alphabet_letters, k):\n",
    "    E = Alphabet(alphabet_letters)\n",
    "    print(repr(E))\n",
    "    print(E)\n",
    "    E_pow_k = len(E) ** k\n",
    "    E_chars = list(E)\n",
    "    string_length = random.randint(E_pow_k, 2 * E_pow_k) # Let's use a random length to match the topic's case\n",
    "    string_arr = [random.choice(E_chars) for _ in range(string_length)]\n",
    "    prev_string = string_arr[:]\n",
    "    print('String (part):')\n",
    "    print(string_arr[:10], string_arr[-10:])\n",
    "\n",
    "    result = most_common_substring(string_arr, E, k)\n",
    "    print(string_arr[:10], string_arr[-10:])  # Check if an alphabet hasn't changed\n",
    "    print('Is the same?:', string_arr == prev_string)\n",
    "\n",
    "    print('\\n===== Final results: =====')\n",
    "    print('Most common substring:', result[0])\n",
    "    print('Occerrences:', result[1])\n",
    "    print('Real occurences of the result string:', ''.join(prev_string).count(result[0])) # If the same as above, an algorithm is correct"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Alphabet(abcdefghijklmnopqrstuvwxyz)\n",
      "a: 0\n",
      "b: 1\n",
      "c: 2\n",
      "d: 3\n",
      "e: 4\n",
      "f: 5\n",
      "g: 6\n",
      "h: 7\n",
      "i: 8\n",
      "j: 9\n",
      "k: 10\n",
      "l: 11\n",
      "m: 12\n",
      "n: 13\n",
      "o: 14\n",
      "p: 15\n",
      "q: 16\n",
      "r: 17\n",
      "s: 18\n",
      "t: 19\n",
      "u: 20\n",
      "v: 21\n",
      "w: 22\n",
      "x: 23\n",
      "y: 24\n",
      "z: 25\n",
      "String (part):\n",
      "['s', 'f', 'w', 'b', 't', 'e', 'q', 'q', 'o', 'g'] ['u', 'y', 'q', 's', 'u', 'w', 'o', 'n', 'm', 'q']\n",
      "['s', 'f', 'w', 'b', 't', 'e', 'q', 'q', 'o', 'g'] ['u', 'y', 'q', 's', 'u', 'w', 'o', 'n', 'm', 'q']\n",
      "Is the same?: True\n",
      "\n",
      "===== Final results: =====\n",
      "Most common substring: ccte\n",
      "Occerrences: 11\n",
      "Real occurences of the result string: 11\n"
     ]
    }
   ],
   "source": [
    "from string import ascii_lowercase\n",
    "\n",
    "test(ascii_lowercase, 4)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}